package vip.zhenzicheng.algorithm.demo.find;

import vip.zhenzicheng.algorithm.util.ArrayUtils;

/**
 * 二分法
 *
 * @author zhenzicheng
 * @date: 2022-05-17 13:58
 */
public class BSExist {
  public static void main(String[] args) {
    int[] arr = ArrayUtils.getRandomArray(100, 500);

    if (find(arr, 2) == contains(arr, 2)) {
      System.out.println("accept！");
    } else {
      System.out.println("error!");
    }

  }

  /**
   * 二分查找
   */
  public static boolean find(int[] arr, int num) {
    if (arr == null || arr.length == 0) {
      return false;
    }
    int L = 0;
    int R = arr.length - 1;
    while (L <= R) {
      int mid = (L + R) / 2;
      if (arr[mid] == num) {
        return true;
      } else if (arr[mid] < num) {
        L = mid + 1;
      } else {
        R = mid - 1;
      }
    }
    return false;
  }

  /**
   * 验证
   */
  public static boolean contains(int[] sortedArr, int num) {
    for (int cur : sortedArr) {
      if (cur == num) {
        return true;
      }
    }
    return false;
  }
}
